/*
  Copyright (c) 2009-2017 Dave Gamble and cJSON contributors

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.
*/

/* 
 * cJSON Utilities Implementation
 * This file provides additional functionality for cJSON library including:
 * 1. JSON Pointer (RFC 6901) implementation for navigating JSON documents
 * 2. JSON Patch (RFC 6902) implementation for applying modifications to JSON documents
 * 3. JSON Merge Patch (RFC 7396) implementation for describing and applying partial modifications
 */

/* disable warnings about old C89 functions in MSVC */
#if !defined(_CRT_SECURE_NO_DEPRECATE) && defined(_MSC_VER)
#define _CRT_SECURE_NO_DEPRECATE
#endif

#ifdef __GNUCC__
#pragma GCC visibility push(default)
#endif
#if defined(_MSC_VER)
#pragma warning (push)
/* disable warning about single line comments in system headers */
#pragma warning (disable : 4001)
#endif

/* 
 * Compiler-specific settings:
 * 1. Disable deprecation warnings for MSVC compiler
 * 2. Set GCC visibility to default for shared library exports
 * 3. Disable specific warnings in MSVC related to single line comments
 */

/* Standard C library headers */
/* Character type functions (tolower, etc.) */
#include <ctype.h>   
/* String manipulation functions (strlen, strcpy, etc.) */   
#include <string.h>  
  /* Standard library functions (malloc, free, etc.) */   
#include <stdio.h>      
/* Standard input/output functions (sprintf, etc.) */
#include <limits.h>     
/* Constants for integral types (ULONG_MAX, etc.) */
#include <math.h>   
/* Mathematical functions (fabs, etc.) */ 
#include <float.h>
/* Floating-point constants (DBL_EPSILON, etc.) */      
#include <math.h>       
/* Additional mathematical functions */

#if defined(_MSC_VER)
#pragma warning (pop)
#endif
#ifdef __GNUCC__
#pragma GCC visibility pop
#endif

/* cJSON Utilities header file */
#include "cJSON_Utils.h"

/* define our own boolean type */
#ifdef true
#undef true
#endif
#define true ((cJSON_bool)1)

#ifdef false
#undef false
#endif
#define false ((cJSON_bool)0)

/* 
 * Duplicate a string using cJSON's memory allocation functions
 * This function creates a copy of the input string by:
 * 1. Calculating the length of the input string plus null terminator
 * 2. Allocating memory using cJSON_malloc
 * 3. Copying the string content to the newly allocated memory
 * 4. Returning the pointer to the copied string
 * Returns NULL if memory allocation fails
 */
static unsigned char* cJSONUtils_strdup(const unsigned char* const string)
{
    size_t length = 0;              /* Length of the string to duplicate */
    unsigned char *copy = NULL;     /* Pointer to the duplicated string */

    length = strlen((const char*)string) + sizeof("");  /* Calculate string length including null terminator */
    copy = (unsigned char*) cJSON_malloc(length);       /* Allocate memory for the copy */
    if (copy == NULL)               /* Check if memory allocation succeeded */
    {
        return NULL;                /* Return NULL on allocation failure */
    }
    memcpy(copy, string, length);   /* Copy the string content to allocated memory */

    return copy;                    /* Return pointer to the duplicated string */
}

/* 
 * String comparison function that handles NULL pointers correctly
 * This function compares two strings with the following behavior:
 * 1. NULL pointers are considered unequal to any value including other NULLs
 * 2. Identical pointers (same address) are considered equal
 * 3. Supports both case-sensitive and case-insensitive comparison
 * Returns 0 if strings are equal, non-zero if they differ
 */
static int compare_strings(const unsigned char *string1, const unsigned char *string2, const cJSON_bool case_sensitive)
{
    /* Handle NULL pointer cases - two NULLs are not considered equal */
    if ((string1 == NULL) || (string2 == NULL))
    {
        return 1;   /* Strings are considered different if either is NULL */
    }

    /* Check if both pointers refer to the same memory location */
    if (string1 == string2)
    {
        return 0;   /* Same pointer means identical strings */
    }

    /* Perform case-sensitive comparison using standard strcmp */
    if (case_sensitive)
    {
        return strcmp((const char*)string1, (const char*)string2);
    }

    /* Perform case-insensitive comparison character by character */
    for(; tolower(*string1) == tolower(*string2); (void)string1++, string2++)
    {
        /* If we've reached the end of the string, they are equal */
        if (*string1 == '\0')
        {
            return 0;
        }
    }

    /* Return difference between lowercase versions of the first differing character */
    return tolower(*string1) - tolower(*string2);
}

/* 
 * Securely compare two floating-point numbers
 * This function compares two double values with proper handling of floating-point precision issues:
 * 1. Uses relative epsilon comparison instead of exact equality
 * 2. Calculates maximum absolute value to scale the epsilon appropriately
 * 3. Returns true if the difference is within acceptable epsilon range
 */
static cJSON_bool compare_double(double a, double b)
{
    double maxVal = fabs(a) > fabs(b) ? fabs(a) : fabs(b);  /* Determine the larger absolute value */
    return (fabs(a - b) <= maxVal * DBL_EPSILON);           /* Compare with scaled epsilon */
}


/* 
 * Compare the next path element of two JSON pointers
 * This function compares JSON pointer segments with proper handling of escape sequences:
 * 1. Two NULL pointers are considered unequal
 * 2. Handles JSON pointer escape sequences ~0 (representing ~) and ~1 (representing /)
 * 3. Compares until the next '/' delimiter or end of string
 * Returns true if the path segments match, false otherwise
 */
static cJSON_bool compare_pointers(const unsigned char *name, const unsigned char *pointer, const cJSON_bool case_sensitive)
{
    /* Check for NULL pointers - two NULLs are considered unequal */
    if ((name == NULL) || (pointer == NULL))
    {
        return false;
    }

    /* Compare characters until we reach '/' delimiter, end of either string, or find a mismatch */
    for (; (*name != '\0') && (*pointer != '\0') && (*pointer != '/'); (void)name++, pointer++) /* compare until next '/' */
    {
        /* Handle JSON pointer escape sequences */
        if (*pointer == '~')
        {
            /* Check for escaped '~' (~0) and '/' (~1) */
            if (((pointer[1] != '0') || (*name != '~')) && ((pointer[1] != '1') || (*name != '/')))
            {
                /* Invalid escape sequence or wrong character in *name */
                return false;
            }
            else
            {
                pointer++;  /* Skip the escape character */
            }
        }
        /* Perform character comparison based on case sensitivity setting */
        else if ((!case_sensitive && (tolower(*name) != tolower(*pointer))) || (case_sensitive && (*name != *pointer)))
        {
            return false;
        }
    }
    /* Check if one string has ended but the other hasn't */
    if (((*pointer != 0) && (*pointer != '/')) != (*name != 0))
    {
        /* One string has ended, the other not */
        return false;;
    }

    return true;  /* Path segments match */
}

/* calculate the length of a string if encoded as JSON pointer with ~0 and ~1 escape sequences */
static size_t pointer_encoded_length(const unsigned char *string)
{
    size_t length;
    for (length = 0; *string != '\0'; (void)string++, length++)
    {
        /* character needs to be escaped? */
        if ((*string == '~') || (*string == '/'))
        {
            length++;
        }
    }

    return length;
}

/* 
 * Copy a string while escaping '~' and '/' with ~0 and ~1 JSON pointer escape codes
 * This function encodes a string for use in JSON pointers by:
 * 1. Replacing '/' with '~1'
 * 2. Replacing '~' with '~0'
 * 3. Copying other characters unchanged
 * The destination buffer must be pre-allocated with sufficient space
 */
static void encode_string_as_pointer(unsigned char *destination, const unsigned char *source)
{
    /* Process each character in the source string until null terminator */
    for (; source[0] != '\0'; (void)source++, destination++)
    {
        /* Replace '/' with '~1' */
        if (source[0] == '/')
        {
            destination[0] = '~';   /* Write '~' */
            destination[1] = '1';   /* Write '1' */
            destination++;          /* Advance destination pointer */
        }
        /* Replace '~' with '~0' */
        else if (source[0] == '~')
        {
            destination[0] = '~';   /* Write '~' */
            destination[1] = '0';   /* Write '0' */
            destination++;          /* Advance destination pointer */
        }
        /* Copy other characters unchanged */
        else
        {
            destination[0] = source[0];
        }
    }

    destination[0] = '\0';  /* Null terminate the destination string */
}

/* 
 * Find a JSON pointer from one object to a target object
 * This function recursively searches through a JSON structure to find a path from the root object to the target object:
 * 1. If object and target are the same, returns empty string ""
 * 2. For arrays, constructs path using array indices
 * 3. For objects, constructs path using property names with proper JSON pointer encoding
 * Returns a dynamically allocated string containing the JSON pointer, or NULL if not found
 */
CJSON_PUBLIC(char *) cJSONUtils_FindPointerFromObjectTo(const cJSON * const object, const cJSON * const target)
{
    size_t child_index = 0;         /* Index counter for array elements */
    cJSON *current_child = 0;       /* Pointer to current child being examined */

    /* Validate input parameters */
    if ((object == NULL) || (target == NULL))
    {
        return NULL;
    }

    /* Check if we've found the target object */
    if (object == target)
    {
        /* Found target at root level - return empty string */
        return (char*)cJSONUtils_strdup((const unsigned char*)"");
    }

    /* Recursively search all children of the object or array */
    for (current_child = object->child; current_child != NULL; (void)(current_child = current_child->next), child_index++)
    {
        unsigned char *target_pointer = (unsigned char*)cJSONUtils_FindPointerFromObjectTo(current_child, target);
        /* Check if target was found in this subtree */
        if (target_pointer != NULL)
        {
            /* Construct full path based on whether parent is an array */
            if (cJSON_IsArray(object))
            {
                /* Reserve enough memory for a 64 bit integer + '/' and '\0' */
                unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + 20 + sizeof("/"));
                /* Check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
                if (child_index > ULONG_MAX)
                {
                    cJSON_free(target_pointer);
                    cJSON_free(full_pointer);
                    return NULL;
                }
                sprintf((char*)full_pointer, "/%lu%s", (unsigned long)child_index, target_pointer); /* /<array_index><path> */
                cJSON_free(target_pointer);

                return (char*)full_pointer;
            }

            /* Construct full path based on whether parent is an object */
            if (cJSON_IsObject(object))
            {
                unsigned char *full_pointer = (unsigned char*)cJSON_malloc(strlen((char*)target_pointer) + pointer_encoded_length((unsigned char*)current_child->string) + 2);
                full_pointer[0] = '/';
                encode_string_as_pointer(full_pointer + 1, (unsigned char*)current_child->string);
                strcat((char*)full_pointer, (char*)target_pointer);
                cJSON_free(target_pointer);

                return (char*)full_pointer;
            }

            /* Reached leaf of the tree, found nothing */
            cJSON_free(target_pointer);
            return NULL;
        }
    }

    /* Target not found in this branch */
    return NULL;
}

/* non broken version of cJSON_GetArrayItem */
static cJSON *get_array_item(const cJSON *array, size_t item)
{
    cJSON *child = array ? array->child : NULL;
    while ((child != NULL) && (item > 0))
    {
        item--;
        child = child->next;
    }

    return child;
}

/* 
 * Decode an array index from a JSON pointer string
 * This function parses a numeric index from a JSON pointer string:
 * 1. Validates that there are no leading zeros (except for "0" itself)
 * 2. Parses consecutive digits into a size_t value
 * 3. Ensures the index is properly terminated by null or '/'
 * Returns 1 on success, 0 on failure
 */
static cJSON_bool decode_array_index_from_pointer(const unsigned char * const pointer, size_t * const index)
{
    size_t parsed_index = 0;   /* Accumulator for the parsed index value */
    size_t position = 0;       /* Current position in the pointer string */

    /* Check for invalid leading zero (e.g., "01", "000", etc.) */
    if ((pointer[0] == '0') && ((pointer[1] != '\0') && (pointer[1] != '/')))
    {
        /* Leading zeroes are not permitted */
        return 0;
    }

    /* Parse consecutive digits into the index value */
    for (position = 0; (pointer[position] >= '0') && (pointer[0] <= '9'); position++)
    {
        parsed_index = (10 * parsed_index) + (size_t)(pointer[position] - '0');

    }

    /* Ensure the index is properly terminated */
    if ((pointer[position] != '\0') && (pointer[position] != '/'))
    {
        return 0;
    }

    *index = parsed_index;  /* Store the parsed index value */

    return 1;  /* Success */
}

/* 
 * Get an item from a JSON object using a JSON pointer string
 * This function navigates a JSON structure following a JSON pointer path:
 * 1. Starts at the given object and follows '/' delimited path segments
 * 2. For arrays, parses numeric indices and retrieves elements
 * 3. For objects, matches property names (with case sensitivity option)
 * 4. Handles JSON pointer escape sequences properly
 * Returns the cJSON item at the specified path, or NULL if not found
 */
static cJSON *get_item_from_pointer(cJSON * const object, const char * pointer, const cJSON_bool case_sensitive)
{
    cJSON *current_element = object;  /* Start navigation from the given object */

    /* Validate input parameter */
    if (pointer == NULL)
    {
        return NULL;
    }

    /* Follow path segments of the pointer */
    while ((pointer[0] == '/') && (current_element != NULL))
    {
        pointer++;  /* Skip the '/' delimiter */
        /* Handle array indexing */
        if (cJSON_IsArray(current_element))
        {
            size_t index = 0;
            /* Parse the array index from the pointer */
            if (!decode_array_index_from_pointer((const unsigned char*)pointer, &index))
            {
                return NULL;
            }

            current_element = get_array_item(current_element, index);
        }
        /* Handle object property access */
        else if (cJSON_IsObject(current_element))
        {
            current_element = current_element->child;
            /* Find matching property name */
            while ((current_element != NULL) && !compare_pointers((unsigned char*)current_element->string, (const unsigned char*)pointer, case_sensitive))
            {
                current_element = current_element->next;
            }
        }
        /* Handle invalid element type */
        else
        {
            return NULL;
        }

        /* Skip to the next path token or end of string */
        while ((pointer[0] != '\0') && (pointer[0] != '/'))
        {
            pointer++;
        }
    }

    return current_element;  /* Return the found element or NULL */
}

/* 
 * Get an item from a JSON object using a JSON pointer string (case-insensitive)
 * This function provides public access to get_item_from_pointer with case-insensitive matching:
 * 1. Takes a JSON object and a JSON pointer string
 * 2. Navigates the JSON structure following the pointer path
 * 3. Property name matching is case-insensitive
 * Returns the cJSON item at the specified path, or NULL if not found
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointer(cJSON * const object, const char *pointer)
{
    return get_item_from_pointer(object, pointer, false);  /* Call with case_insensitive = false */
}

/* 
 * Get an item from a JSON object using a JSON pointer string (case-sensitive)
 * This function provides public access to get_item_from_pointer with case-sensitive matching:
 * 1. Takes a JSON object and a JSON pointer string
 * 2. Navigates the JSON structure following the pointer path
 * 3. Property name matching is case-sensitive
 * Returns the cJSON item at the specified path, or NULL if not found
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GetPointerCaseSensitive(cJSON * const object, const char *pointer)
{
    return get_item_from_pointer(object, pointer, true);  /* Call with case_insensitive = true */
}

/* 
 * JSON Patch implementation helper function
 * Decode JSON pointer escape sequences in-place:
 * 1. Replaces '~0' sequences with '~'
 * 2. Replaces '~1' sequences with '/'
 * 3. Modifies the input string directly
 * 4. Handles invalid escape sequences by returning early
 */
static void decode_pointer_inplace(unsigned char *string)
{
    unsigned char *decoded_string = string;  /* Pointer to the output position in the string */

    /* Validate input parameter */
    if (string == NULL) {
        return;
    }

    /* Process each character in the string */
    for (; *string; (void)decoded_string++, string++)
    {
        /* Check for escape sequence */
        if (string[0] == '~')
        {
            /* Handle '~0' -> '~' */
            if (string[1] == '0')
            {
                decoded_string[0] = '~';
            }
            /* Handle '~1' -> '/' */
            else if (string[1] == '1')
            {
                decoded_string[1] = '/';
            }
            /* Handle invalid escape sequence */
            else
            {
                /* Invalid escape sequence */
                return;
            }

            string++;  /* Skip the escape character */
        }
    }

    decoded_string[0] = '\0';  /* Null terminate the decoded string */
}

/* 
 * Non-broken version of cJSON_DetachItemFromArray
 * This function detaches an item from a cJSON array without deleting it:
 * 1. Finds the item at the specified index
 * 2. Removes it from the linked list structure
 * 3. Updates all necessary pointers to maintain list integrity
 * 4. Clears the detached item's pointers to avoid dangling references
 * Returns the detached cJSON item, or NULL if index is out of bounds
 */
static cJSON *detach_item_from_array(cJSON *array, size_t which)
{
    cJSON *c = array->child;  /* Start with the first child */
    /* Navigate to the specified index */
    while (c && (which > 0))
    {
        c = c->next;
        which--;
    }
    /* Check if item exists at the specified index */
    if (!c)
    {
        /* Item doesn't exist */
        return NULL;
    }
    /* Update previous element's next pointer */
    if (c != array->child)
    {
        /* Not the first element */
        c->prev->next = c->next;
    }
    /* Update next element's previous pointer */
    if (c->next)
    {
        c->next->prev = c->prev;
    }
    /* Update array's child pointer if removing the first element */
    if (c == array->child)
    {
        array->child = c->next;
    }
    /* Update the new last element's previous pointer */
    else if (c->next == NULL)
    {
        array->child->prev = c->prev;
    }
    /* Make sure the detached item doesn't point anywhere anymore */
    c->prev = c->next = NULL;

    return c;  /* Return the detached item */
}

/* 
 * Detach an item at the given JSON pointer path
 * This function removes an item from a JSON structure at the specified path:
 * 1. Splits the path into parent and child components
 * 2. Navigates to the parent object
 * 3. Decodes JSON pointer escape sequences in the child name
 * 4. Removes the child item from its parent (array or object)
 * 5. Properly cleans up allocated memory
 * Returns the detached cJSON item, or NULL if path is invalid
 */
static cJSON *detach_path(cJSON *object, const unsigned char *path, const cJSON_bool case_sensitive)
{
    unsigned char *parent_pointer = NULL;   /* Copy of path for parent navigation */
    unsigned char *child_pointer = NULL;    /* Pointer to child segment of path */
    cJSON *parent = NULL;                   /* Parent object of the item to detach */
    cJSON *detached_item = NULL;            /* The detached item */

    /* Copy path and split it in parent and child components */
    parent_pointer = cJSONUtils_strdup(path);
    if (parent_pointer == NULL) {
        goto cleanup;
    }

    child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/'); /* Find last '/' */
    if (child_pointer == NULL)
    {
        goto cleanup;
    }
    /* Split strings by null-terminating the parent path */
    child_pointer[0] = '\0';
    child_pointer++;

    /* Navigate to the parent object */
    parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive);
    /* Decode JSON pointer escape sequences in the child name */
    decode_pointer_inplace(child_pointer);

    /* Detach the item based on parent type */
    if (cJSON_IsArray(parent))
    {
        size_t index = 0;
        /* Parse array index from the child pointer */
        if (!decode_array_index_from_pointer(child_pointer, &index))
        {
            goto cleanup;
        }
        detached_item = detach_item_from_array(parent, index);
    }
    else if (cJSON_IsObject(parent))
    {
        /* Detach item from object using cJSON library function */
        detached_item = cJSON_DetachItemFromObject(parent, (char*)child_pointer);
    }
    else
    {
        /* Couldn't find object to remove child from. */
        goto cleanup;
    }

cleanup:
    /* Clean up allocated memory */
    if (parent_pointer != NULL)
    {
        cJSON_free(parent_pointer);
    }

    return detached_item;  /* Return the detached item or NULL */
}

/* 
 * Sort a cJSON object's members using merge sort algorithm
 * This function sorts the members of a cJSON object by their keys:
 * 1. Uses merge sort for O(n log n) performance
 * 2. Handles already sorted lists efficiently
 * 3. Supports both case-sensitive and case-insensitive sorting
 * 4. Maintains proper linked list pointers during sorting
 * Returns the sorted list head
 */
static cJSON *sort_list(cJSON *list, const cJSON_bool case_sensitive)
{
    cJSON *first = list;        /* First half of the list */
    cJSON *second = list;       /* Second half of the list */
    cJSON *current_item = list; /* Current item during traversal */
    cJSON *result = list;       /* Result list head */
    cJSON *result_tail = NULL;  /* Tail of the result list */

    /* Handle base cases: empty list or single element */
    if ((list == NULL) || (list->next == NULL))
    {
        /* One entry is sorted already. */
        return result;
    }

    /* Check if list is already sorted to avoid unnecessary work */
    while ((current_item != NULL) && (current_item->next != NULL) && (compare_strings((unsigned char*)current_item->string, (unsigned char*)current_item->next->string, case_sensitive) < 0))
    {
        /* Test for list sorted. */
        current_item = current_item->next;
    }
    /* Return early if list is already sorted */
    if ((current_item == NULL) || (current_item->next == NULL))
    {
        /* Leave sorted lists unmodified. */
        return result;
    }

    /* Reset pointer to the beginning */
    current_item = list;
    /* Use two-pointer technique to find the middle of the list */
    while (current_item != NULL)
    {
        /* Walk two pointers to find the middle. */
        second = second->next;
        current_item = current_item->next;
        /* Advances current_item two steps at a time */
        if (current_item != NULL)
        {
            current_item = current_item->next;
        }
    }
    /* Split the list into two halves */
    if ((second != NULL) && (second->prev != NULL))
    {
        /* Split the lists */
        second->prev->next = NULL;
        second->prev = NULL;
    }

    /* Recursively sort the sub-lists. */
    first = sort_list(first, case_sensitive);
    second = sort_list(second, case_sensitive);
    result = NULL;

    /* Merge the sorted sub-lists */
    while ((first != NULL) && (second != NULL))
    {
        cJSON *smaller = NULL;
        /* Compare keys to determine which element is smaller */
        if (compare_strings((unsigned char*)first->string, (unsigned char*)second->string, case_sensitive) < 0)
        {
            smaller = first;
        }
        else
        {
            smaller = second;
        }

        /* Add the smaller element to the result list */
        if (result == NULL)
        {
            /* Start merged list with the smaller element */
            result_tail = smaller;
            result = smaller;
        }
        else
        {
            /* Add smaller element to the list */
            result_tail->next = smaller;
            smaller->prev = result_tail;
            result_tail = smaller;
        }

        /* Advance the appropriate list pointer */
        if (first == smaller)
        {
            first = first->next;
        }
        else
        {
            second = second->next;
        }
    }

    /* Append any remaining elements from the first list */
    if (first != NULL)
    {
        /* Append rest of first list. */
        if (result == NULL)
        {
            return first;
        }
        result_tail->next = first;
        first->prev = result_tail;
    }
    /* Append any remaining elements from the second list */
    if (second != NULL)
    {
        /* Append rest of second list */
        if (result == NULL)
        {
            return second;
        }
        result_tail->next = second;
        second->prev = result_tail;
    }

    return result;  /* Return the sorted list */
}

/* 
 * Sort a cJSON object's members recursively
 * This function sorts all members of a cJSON object by their keys:
 * 1. Checks for NULL object to prevent crashes
 * 2. Calls sort_list to perform the actual sorting using merge sort
 * 3. Updates the object's child pointer to point to the new sorted list head
 * The sorting can be case-sensitive or case-insensitive based on the flag
 */
static void sort_object(cJSON * const object, const cJSON_bool case_sensitive)
{
    /* Check for NULL object to prevent crashes */
    if (object == NULL)
    {
        return;
    }
    /* Sort the object's child list and update the child pointer */
    object->child = sort_list(object->child, case_sensitive);
}

/* 
 * Compare two cJSON objects for equality
 * This function performs a deep comparison of two cJSON objects:
 * 1. Handles NULL comparisons correctly
 * 2. Compares object types first
 * 3. For each type (number, string, array, object, etc.), uses appropriate comparison method
 * 4. Recursively compares nested structures
 * 5. Sorts objects before comparing to ensure consistent ordering
 * Returns true if equal, false otherwise
 */
static cJSON_bool compare_json(cJSON *a, cJSON *b, const cJSON_bool case_sensitive)
{
    /* Handle NULL comparisons */
    if ((a == NULL) || (b == NULL))
    {
        return (a == b); /* Both NULL are equal, otherwise not equal */
    }
    
    /* Compare basic types */
    if ((a->type & 0xFF) != (b->type & 0xFF))
    {
        return false; /* Different types are not equal */
    }
    
    /* Compare based on type */
    switch (a->type & 0xFF)
    {
        /* Compare numbers using integer and double precision */
        case cJSON_Number:
            if ((a->valueint != b->valueint) || (!compare_double(a->valuedouble, b->valuedouble)))
            {
                return false; /* Numeric values differ */
            }
            else
            {
                return true; /* Numbers are equal */
            }

        /* Compare strings */
        case cJSON_String:
            if (strcmp(a->valuestring, b->valuestring) != 0)
            {
                return false; /* String values differ */
            }
            else
            {
                return true; /* Strings are equal */
            }

        /* Recursively compare arrays */
        case cJSON_Array:
            /* Iterate through array elements */
            for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next)
            {
                cJSON_bool identical = compare_json(a, b, case_sensitive);
                if (!identical)
                {
                    return false; /* Array elements differ */
                }
            }
            /* Check if arrays have different lengths */
            if ((a != NULL) || (b != NULL))
            {
                return false; /* One array is longer than the other */
            }
            else
            {
                return true; /* Arrays are equal */
            }

        /* Compare objects by sorting and then comparing members */
        case cJSON_Object:
            /* Sort both objects to ensure consistent member ordering */
            sort_object(a, case_sensitive);
            sort_object(b, case_sensitive);
            /* Iterate through object members */
            for ((void)(a = a->child), b = b->child; (a != NULL) && (b != NULL); (void)(a = a->next), b = b->next)
            {
                cJSON_bool identical = false;
                /* Compare member names first */
                if (compare_strings((unsigned char*)a->string, (unsigned char*)b->string, case_sensitive))
                {
                    return false; /* Member names differ */
                }
                /* Compare member values */
                identical = compare_json(a, b, case_sensitive);
                if (!identical)
                {
                    return false; /* Member values differ */
                }
            }
            /* Check if objects have different number of members */
            if ((a != NULL) || (b != NULL))
            {
                return false; /* Objects have different member counts */
            }
            else
            {
                return true; /* Objects are equal */
            }

        /* Default case for null, true or false */
        default:
            break;
    }

    /* null, true or false */
    return true;
}

/* 
 * Insert an item into a cJSON array at a specific index
 * This function inserts a new cJSON item into an array at the specified position:
 * 1. Navigates to the element at the given index
 * 2. If index is beyond array length, appends to end using cJSON_AddItemToArray
 * 3. Otherwise, inserts the item at the specified position by adjusting linked list pointers
 * 4. Properly handles edge cases like inserting at the beginning of the array
 * Returns true on success, false on failure
 */
static cJSON_bool insert_item_in_array(cJSON *array, size_t which, cJSON *newitem)
{
    cJSON *child = array->child;  /* Current child element during traversal */
    while (child && (which > 0))
    {
        child = child->next;
        which--;
    }
    /* If index is beyond array length, append to end */
    if (which > 0)
    {
        /* item is after the end of the array */
        return 0;
    }
    if (child == NULL)
    {
        cJSON_AddItemToArray(array, newitem);
        return 1;
    }

    /* insert into the linked list */
    newitem->next = child;          /* Link new item to the current item */
    newitem->prev = child->prev;    /* Link new item to the previous item */
    child->prev = newitem;          /* Update current item's previous pointer */
    /* Update previous item's next pointer or array's child pointer */
    /* was it at the beginning */
    if (child == array->child)
    {
        array->child = newitem;          /* Update array's child pointer */
    }
    else
    {
        newitem->prev->next = newitem;  /* Link previous item to new item */
    }

    return 1;
}

/* 
 * Get a cJSON object member by name
 * This function retrieves a member from a cJSON object by its name:
 * 1. Iterates through all members of the object
 * 2. Compares member names with the requested name
 * 3. Supports both case-sensitive and case-insensitive matching
 * 4. Returns the first matching member or NULL if not found
 * This is a non-broken version of cJSON_GetObjectItem with better error handling
 */
static cJSON *get_object_item(const cJSON * const object, const char* name, const cJSON_bool case_sensitive)
{
    if (case_sensitive)
    {
        return cJSON_GetObjectItemCaseSensitive(object, name);
    }

    return cJSON_GetObjectItem(object, name);
}

enum patch_operation { INVALID, ADD, REMOVE, REPLACE, MOVE, COPY, TEST };

/* 
 * Decode a JSON patch operation (like 'move' or 'copy')
 * This function processes a JSON patch operation that requires a 'from' path:
 * 1. Extracts the 'path' field from the patch object
 * 2. Extracts the 'from' field from the patch object
 * 3. Duplicates and decodes the 'from' path for use in patch operations
 * 4. Handles memory allocation and error checking
 * Used primarily for 'move' and 'copy' operations in JSON Patch (RFC 6902)
 * Returns true on success, false on failure
 */
static enum patch_operation decode_patch_operation(const cJSON * const patch, const cJSON_bool case_sensitive)
{
    cJSON *operation = get_object_item(patch, "op", case_sensitive);
    if (!cJSON_IsString(operation))
    {
        return INVALID;  /* Missing or invalid 'op' field */
    }

    if (strcmp(operation->valuestring, "add") == 0)
    {
        return ADD;
    }

    if (strcmp(operation->valuestring, "remove") == 0)
    {
        return REMOVE;
    }

    if (strcmp(operation->valuestring, "replace") == 0)
    {
        return REPLACE;
    }

    if (strcmp(operation->valuestring, "move") == 0)
    {
        return MOVE;
    }

    if (strcmp(operation->valuestring, "copy") == 0)
    {
        return COPY;
    }

    if (strcmp(operation->valuestring, "test") == 0)
    {
        return TEST;
    }

    return INVALID;  /* Unknown operation */
}

/* overwrite and existing item with another one and free resources on the way */
/* 
 * Overwrite a cJSON item with another item's content
 * This function replaces the content of an existing cJSON item with that of another:
 * 1. Deletes the current content of the target item
 * 2. Duplicates the source item's content
 * 3. Updates all fields of the target item with the duplicated content
 * 4. Preserves the target item's position in the data structure
 * Used in JSON Patch operations where an existing value needs to be replaced
 */
static void overwrite_item(cJSON * const root, const cJSON replacement)
{
    if (root == NULL)
    {
        return;
    }

    if (root->string != NULL)
    {
        cJSON_free(root->string);
    }
    if (root->valuestring != NULL)
    {
        cJSON_free(root->valuestring);
    }
    if (root->child != NULL)
    {
        cJSON_Delete(root->child);
    }

    memcpy(root, &replacement, sizeof(cJSON));
}

/* 
 * Apply a single JSON patch operation to an object
 * This function implements the core JSON Patch (RFC 6902) functionality:
 * 1. Parses the patch operation (add, remove, replace, move, copy, test)
 * 2. Locates the target item using the path
 * 3. Executes the appropriate operation on the target
 * 4. Handles complex operations like moving/copying items between locations
 * 5. Manages memory allocation and error recovery
 * Returns 0 on success, non-zero error code on failure
 */
static int apply_patch(cJSON *object, const cJSON *patch, const cJSON_bool case_sensitive)
{
    cJSON *path = NULL;              /* Path field from the patch */
    cJSON *value = NULL;             /* Value field from the patch */
    cJSON *parent = NULL;            /* Parent object of the target item */
    enum patch_operation opcode = INVALID;  /* Decoded patch operation */
    unsigned char *parent_pointer = NULL;  /* Copy of path for parent navigation */
    unsigned char *child_pointer = NULL;   /* Child portion of the path */
    int status = 0;                  /* Operation result status */

    /* Extract and validate the path from the patch */
    path = get_object_item(patch, "path", case_sensitive);
    if (!cJSON_IsString(path))
    {
        /* malformed patch. */
        status = 2;
        goto cleanup;
    }

    /* Determine the operation type */
    opcode = decode_patch_operation(patch, case_sensitive);
    if (opcode == INVALID)
    {
        status = 3;
        goto cleanup;
    }
    else if (opcode == TEST)
    {
        /* compare value: {...} with the given path */
        status = !compare_json(get_item_from_pointer(object, path->valuestring, case_sensitive), get_object_item(patch, "value", case_sensitive), case_sensitive);
        goto cleanup;
    }

    /* Special handling for root object replacement */
    if (path->valuestring[0] == '\0')
    {
        if (opcode == REMOVE)
        {
            static const cJSON invalid = { NULL, NULL, NULL, cJSON_Invalid, NULL, 0, 0, NULL};

            overwrite_item(object, invalid);

            status = 0;
            goto cleanup;
        }

        if ((opcode == REPLACE) || (opcode == ADD))
        {
            value = get_object_item(patch, "value", case_sensitive);
            if (value == NULL)
            {
                /* missing "value" for add/replace. */
                status = 7;
                goto cleanup;
            }

            value = cJSON_Duplicate(value, 1);
            if (value == NULL)
            {
                /* out of memory for add/replace. */
                status = 8;
                goto cleanup;
            }

            overwrite_item(object, *value);

            /* delete the duplicated value */
            cJSON_free(value);
            value = NULL;

            /* the string "value" isn't needed */
            if (object->string != NULL)
            {
                cJSON_free(object->string);
                object->string = NULL;
            }

            status = 0;
            goto cleanup;
        }
    }

    /* Handle remove and replace operations that need to delete existing items */
    if ((opcode == REMOVE) || (opcode == REPLACE))
    {
        /* Get rid of old. */
        cJSON *old_item = detach_path(object, (unsigned char*)path->valuestring, case_sensitive);
        if (old_item == NULL)
        {
            status = 13;
            goto cleanup;
        }
        cJSON_Delete(old_item);
        if (opcode == REMOVE)
        {
            /* For Remove, this job is done. */
            status = 0;
            goto cleanup;
        }
    }

    /* Handle move and copy operations that use a "from" field */
    if ((opcode == MOVE) || (opcode == COPY))
    {
        cJSON *from = get_object_item(patch, "from", case_sensitive);
        if (from == NULL)
        {
            /* missing "from" for copy/move. */
            status = 4;
            goto cleanup;
        }

        if (opcode == MOVE)
        {
            value = detach_path(object, (unsigned char*)from->valuestring, case_sensitive);
        }
        if (opcode == COPY)
        {
            value = get_item_from_pointer(object, from->valuestring, case_sensitive);
        }
        if (value == NULL)
        {
            /* missing "from" for copy/move. */
            status = 5;
            goto cleanup;
        }
        if (opcode == COPY)
        {
            value = cJSON_Duplicate(value, 1);
        }
        if (value == NULL)
        {
            /* out of memory for copy/move. */
            status = 6;
            goto cleanup;
        }
    }
    else /* Add/Replace operations use a "value" field */
    {
        value = get_object_item(patch, "value", case_sensitive);
        if (value == NULL)
        {
            /* missing "value" for add/replace. */
            status = 7;
            goto cleanup;
        }
        value = cJSON_Duplicate(value, 1);
        if (value == NULL)
        {
            /* out of memory for add/replace. */
            status = 8;
            goto cleanup;
        }
    }

    /* Now, just add "value" to "path". */

    /* Split pointer into parent and child components */
    parent_pointer = cJSONUtils_strdup((unsigned char*)path->valuestring);
    if (parent_pointer) {
        child_pointer = (unsigned char*)strrchr((char*)parent_pointer, '/');
    }
    if (child_pointer != NULL)
    {
        child_pointer[0] = '\0';
        child_pointer++;
    }
    parent = get_item_from_pointer(object, (char*)parent_pointer, case_sensitive);
    decode_pointer_inplace(child_pointer);

    /* Perform the actual addition/insertion based on parent type */
    if ((parent == NULL) || (child_pointer == NULL))
    {
        /* Couldn't find object to add to. */
        status = 9;
        goto cleanup;
    }
    else if (cJSON_IsArray(parent))
    {
        if (strcmp((char*)child_pointer, "-") == 0)
        {
            cJSON_AddItemToArray(parent, value);
            value = NULL;
        }
        else
        {
            size_t index = 0;
            if (!decode_array_index_from_pointer(child_pointer, &index))
            {
                status = 11;
                goto cleanup;
            }

            if (!insert_item_in_array(parent, index, value))
            {
                status = 10;
                goto cleanup;
            }
            value = NULL;
        }
    }
    else if (cJSON_IsObject(parent))
    {
        if (case_sensitive)
        {
            cJSON_DeleteItemFromObjectCaseSensitive(parent, (char*)child_pointer);
        }
        else
        {
            cJSON_DeleteItemFromObject(parent, (char*)child_pointer);
        }
        cJSON_AddItemToObject(parent, (char*)child_pointer, value);
        value = NULL;
    }
    else /* parent is not an object */
    {
        /* Couldn't find object to add to. */
        status = 9;
        goto cleanup;
    }

cleanup:
    if (value != NULL)
    {
        cJSON_Delete(value);
    }
    if (parent_pointer != NULL)
    {
        cJSON_free(parent_pointer);
    }

    return status;
}

/* 
 * Apply a series of JSON patches to an object (case-insensitive)
 * This function implements the public API for applying JSON Patch (RFC 6902):
 * 1. Takes an object to modify and an array of patch operations
 * 2. Iterates through each patch operation
 * 3. Applies each patch using the internal apply_patch function
 * 4. Uses case-insensitive matching for object member names
 * 5. Continues applying patches even if some fail (but reports overall failure)
 * Returns true if all patches were applied successfully, false otherwise
 */
CJSON_PUBLIC(int) cJSONUtils_ApplyPatches(cJSON * const object, const cJSON * const patches)
{
    const cJSON *current_patch = NULL;  /* Current patch being processed */
    int status = 0;                     /* Overall result of patch application */

    /* Validate input parameters */
    if (!cJSON_IsArray(patches))
    {
        /* malformed patches. */
        return 1;
    }

    if (patches != NULL)
    {
        current_patch = patches->child;
    }

    /* Loop through all patches in the array */
    while (current_patch != NULL)
    {
        /* Apply the current patch with case-insensitive matching */
        status = apply_patch(object, current_patch, false);
        if (status != 0)
        {
            return status;  /* Return failure status immediately */
        }
        current_patch = current_patch->next;
    }

    return 0;  /* Return success */
}

/* 
 * Apply a series of JSON patches to an object (case-sensitive)
 * This function implements the public API for applying JSON Patch (RFC 6902):
 * 1. Takes an object to modify and an array of patch operations
 * 2. Iterates through each patch operation
 * 3. Applies each patch using the internal apply_patch function
 * 4. Uses case-sensitive matching for object member names (unlike cJSONUtils_ApplyPatches)
 * 5. Continues applying patches even if some fail (but reports overall failure)
 * Returns true if all patches were applied successfully, false otherwise
 */
CJSON_PUBLIC(int) cJSONUtils_ApplyPatchesCaseSensitive(cJSON * const object, const cJSON * const patches)
{
    const cJSON *current_patch = NULL;  /* Current patch being processed */
    int status = 0;                     /* Status of patch application */

    /* Validate input parameters */
    if ((object == NULL) || (patches == NULL))
    {
        return 1;
    }

    if (!cJSON_IsArray(patches))
    {
        /* malformed patches. */
        return 1;
    }

    /* Loop through all patches in the array */
    if (patches != NULL)
    {
        current_patch = patches->child;
    }

    while (current_patch != NULL)
    {
        /* Apply the current patch with case-sensitive matching */
        status = apply_patch(object, current_patch, true);
        if (status != 0)
        {
            return status;  /* Return failure status immediately */
        }
        current_patch = current_patch->next;
    }

    return 0;  /* Return success */
}

static void compose_patch(cJSON * const patches, const unsigned char * const operation, const unsigned char * const path, const unsigned char *suffix, const cJSON * const value)
{
    cJSON *patch = NULL;

    if ((patches == NULL) || (operation == NULL) || (path == NULL))
    {
        return;
    }

    patch = cJSON_CreateObject();
    if (patch == NULL)
    {
        return;
    }
    cJSON_AddItemToObject(patch, "op", cJSON_CreateString((const char*)operation));

    if (suffix == NULL)
    {
        cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)path));
    }
    else
    {
        size_t suffix_length = pointer_encoded_length(suffix);
        size_t path_length = strlen((const char*)path);
        unsigned char *full_path = (unsigned char*)cJSON_malloc(path_length + suffix_length + sizeof("/"));

        sprintf((char*)full_path, "%s/", (const char*)path);
        encode_string_as_pointer(full_path + path_length + 1, suffix);

        cJSON_AddItemToObject(patch, "path", cJSON_CreateString((const char*)full_path));
        cJSON_free(full_path);
    }

    if (value != NULL)
    {
        cJSON_AddItemToObject(patch, "value", cJSON_Duplicate(value, 1));
    }
    cJSON_AddItemToArray(patches, patch);
}

/* 
 * Add a JSON patch operation to a patches array
 * This function provides a public API for manually constructing JSON patches:
 * 1. Takes an array to which the patch will be added
 * 2. Accepts operation type, path, and value as parameters
 * 3. Delegates to compose_patch to create and add the patch
 * 4. Does not support "from" parameter (useful for add, remove, replace, test operations)
 * This allows users to build custom patch sequences programmatically
 */
CJSON_PUBLIC(void) cJSONUtils_AddPatchToArray(cJSON *array, const char * const operation, const char * const path, const cJSON * const value)
{
    /* Delegate to compose_patch with NULL from parameter */
    compose_patch(array, (const unsigned char*)operation, (const unsigned char*)path, value, NULL);
}

/* 
 * Recursively create JSON patches to transform one cJSON structure into another
 * This function implements the core logic for JSON Patch generation (RFC 6902):
 * 1. Compares two cJSON structures recursively
 * 2. Generates appropriate patch operations (add, remove, replace) to transform 'from' into 'to'
 * 3. Handles all cJSON types: objects, arrays, strings, numbers, booleans, null
 * 4. Properly encodes JSON pointer paths for special characters
 * 5. Supports both case-sensitive and case-insensitive comparisons
 * 6. Manages memory allocation for path strings
 * Patches are added to the 'patches' array which can then be used to apply the transformation
 */
static void create_patches(cJSON * const patches, const unsigned char * const path, cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive)
{
    if ((from == NULL) || (to == NULL))
    {
        return;
    }

    if ((from->type & 0xFF) != (to->type & 0xFF))
    {
        compose_patch(patches, (const unsigned char*)"replace", path, 0, to);
        return;
    }

    switch (from->type & 0xFF)
    {
        case cJSON_Number:
            if ((from->valueint != to->valueint) || !compare_double(from->valuedouble, to->valuedouble))
            {
                compose_patch(patches, (const unsigned char*)"replace", path, NULL, to);
            }
            return;

        case cJSON_String:
            if (strcmp(from->valuestring, to->valuestring) != 0)
            {
                compose_patch(patches, (const unsigned char*)"replace", path, NULL, to);
            }
            return;

        case cJSON_Array:
        {
            size_t index = 0;
            cJSON *from_child = from->child;
            cJSON *to_child = to->child;
            unsigned char *new_path = (unsigned char*)cJSON_malloc(strlen((const char*)path) + 20 + sizeof("/")); /* Allow space for 64bit int. log10(2^64) = 20 */

            /* generate patches for all array elements that exist in both "from" and "to" */
            for (index = 0; (from_child != NULL) && (to_child != NULL); (void)(from_child = from_child->next), (void)(to_child = to_child->next), index++)
            {
                /* check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
                if (index > ULONG_MAX)
                {
                    cJSON_free(new_path);
                    return;
                }
                sprintf((char*)new_path, "%s/%lu", path, (unsigned long)index); /* path of the current array element */
                create_patches(patches, new_path, from_child, to_child, case_sensitive);
            }

            /* remove leftover elements from 'from' that are not in 'to' */
            for (; (from_child != NULL); (void)(from_child = from_child->next))
            {
                /* check if conversion to unsigned long is valid
                 * This should be eliminated at compile time by dead code elimination
                 * if size_t is an alias of unsigned long, or if it is bigger */
                if (index > ULONG_MAX)
                {
                    cJSON_free(new_path);
                    return;
                }
                sprintf((char*)new_path, "%lu", (unsigned long)index);
                compose_patch(patches, (const unsigned char*)"remove", path, new_path, NULL);
            }
            /* add new elements in 'to' that were not in 'from' */
            for (; (to_child != NULL); (void)(to_child = to_child->next), index++)
            {
                compose_patch(patches, (const unsigned char*)"add", path, (const unsigned char*)"-", to_child);
            }
            cJSON_free(new_path);
            return;
        }

        case cJSON_Object:
        {
            cJSON *from_child = NULL;
            cJSON *to_child = NULL;
            sort_object(from, case_sensitive);
            sort_object(to, case_sensitive);

            from_child = from->child;
            to_child = to->child;
            /* for all object values in the object with more of them */
            while ((from_child != NULL) || (to_child != NULL))
            {
                int diff;
                if (from_child == NULL)
                {
                    diff = 1;
                }
                else if (to_child == NULL)
                {
                    diff = -1;
                }
                else
                {
                    diff = compare_strings((unsigned char*)from_child->string, (unsigned char*)to_child->string, case_sensitive);
                }

                if (diff == 0)
                {
                    /* both object keys are the same */
                    size_t path_length = strlen((const char*)path);
                    size_t from_child_name_length = pointer_encoded_length((unsigned char*)from_child->string);
                    unsigned char *new_path = (unsigned char*)cJSON_malloc(path_length + from_child_name_length + sizeof("/"));

                    sprintf((char*)new_path, "%s/", path);
                    encode_string_as_pointer(new_path + path_length + 1, (unsigned char*)from_child->string);

                    /* create a patch for the element */
                    create_patches(patches, new_path, from_child, to_child, case_sensitive);
                    cJSON_free(new_path);

                    from_child = from_child->next;
                    to_child = to_child->next;
                }
                else if (diff < 0)
                {
                    /* object element doesn't exist in 'to' --> remove it */
                    compose_patch(patches, (const unsigned char*)"remove", path, (unsigned char*)from_child->string, NULL);

                    from_child = from_child->next;
                }
                else
                {
                    /* object element doesn't exist in 'from' --> add it */
                    compose_patch(patches, (const unsigned char*)"add", path, (unsigned char*)to_child->string, to_child);

                    to_child = to_child->next;
                }
            }
            return;
        }

        default:
            break;
    }
}

/* 
 * Generate JSON patches to transform one cJSON structure into another (case-insensitive)
 * This function implements the public API for JSON Patch generation (RFC 6902):
 * 1. Takes two cJSON structures ('from' and 'to')
 * 2. Creates an array to hold the generated patches
 * 3. Delegates to create_patches for the actual patch generation
 * 4. Uses case-insensitive comparison for object member names
 * 5. Returns an array of patch operations that can transform 'from' into 'to'
 * Returns a cJSON array of patches, or NULL on error
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatches(cJSON * const from, cJSON * const to)
{
    cJSON *patches = NULL;  /* Array to hold generated patches */

    /* Validate input parameters */
    if ((from == NULL) || (to == NULL))
    {
        return NULL;  /* Invalid parameters */
    }

    /* Create array to hold the patches */
    patches = cJSON_CreateArray();
    if (patches == NULL)
    {
        return NULL;  /* Memory allocation failed */
    }

    /* Generate patches using empty root path and case-insensitive comparison */
    create_patches(patches, (const unsigned char*)"", from, to, false);

    return patches;  /* Return the generated patches */
}

/* 
 * Generate JSON patches to transform one cJSON structure into another (case-sensitive)
 * This function implements the public API for JSON Patch generation (RFC 6902):
 * 1. Takes two cJSON structures ('from' and 'to')
 * 2. Creates an array to hold the generated patches
 * 3. Delegates to create_patches for the actual patch generation
 * 4. Uses case-sensitive comparison for object member names (unlike cJSONUtils_GeneratePatches)
 * 5. Returns an array of patch operations that can transform 'from' into 'to'
 * Returns a cJSON array of patches, or NULL on error
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GeneratePatchesCaseSensitive(cJSON * const from, cJSON * const to)
{
    cJSON *patches = NULL;  /* Array to hold generated patches */

    /* Validate input parameters */
    if ((from == NULL) || (to == NULL))
    {
        return NULL;  /* Invalid parameters */
    }

    /* Create array to hold the patches */
    patches = cJSON_CreateArray();
    if (patches == NULL)
    {
        return NULL;  /* Memory allocation failed */
    }

    /* Generate patches using empty root path and case-sensitive comparison */
    create_patches(patches, (const unsigned char*)"", from, to, true);

    return patches;  /* Return the generated patches */
}

/* 
 * Sort a cJSON object's members alphabetically (case-insensitive)
 * This function provides a public API for sorting cJSON object members:
 * 1. Takes a cJSON object as input
 * 2. Sorts all members alphabetically by their keys
 * 3. Uses case-insensitive comparison for sorting
 * 4. Delegates to the internal sort_object function
 * Sorting is useful for:
 * - Ensuring consistent object representation
 * - Making JSON comparisons more reliable
 * - Improving readability of serialized JSON
 */
CJSON_PUBLIC(void) cJSONUtils_SortObject(cJSON * const object)
{
    /* Delegate to internal sort_object with case-insensitive comparison */
    sort_object(object, false);
}

/* 
 * Sort a cJSON object's members alphabetically (case-sensitive)
 * This function provides a public API for sorting cJSON object members:
 * 1. Takes a cJSON object as input
 * 2. Sorts all members alphabetically by their keys
 * 3. Uses case-sensitive comparison for sorting (unlike cJSONUtils_SortObject)
 * 4. Delegates to the internal sort_object function
 * Sorting is useful for:
 * - Ensuring consistent object representation
 * - Making JSON comparisons more reliable
 * - Improving readability of serialized JSON
 * The case-sensitive version treats 'A' and 'a' as different characters in sorting
 */
CJSON_PUBLIC(void) cJSONUtils_SortObjectCaseSensitive(cJSON * const object)
{
    /* Delegate to internal sort_object with case-sensitive comparison */
    sort_object(object, true);
}

static cJSON *merge_patch(cJSON *target, const cJSON * const patch, const cJSON_bool case_sensitive)
{
    cJSON *patch_child = NULL;

    if (!cJSON_IsObject(patch))
    {
        /* scalar value, array or NULL, just duplicate */
        cJSON_Delete(target);
        return cJSON_Duplicate(patch, 1);
    }

    if (!cJSON_IsObject(target))
    {
        cJSON_Delete(target);
        target = cJSON_CreateObject();
    }

    patch_child = patch->child;
    while (patch_child != NULL)
    {
        if (cJSON_IsNull(patch_child))
        {
            /* NULL is the indicator to remove a value, see RFC7396 */
            if (case_sensitive)
            {
                cJSON_DeleteItemFromObjectCaseSensitive(target, patch_child->string);
            }
            else
            {
                cJSON_DeleteItemFromObject(target, patch_child->string);
            }
        }
        else
        {
            cJSON *replace_me = NULL;
            cJSON *replacement = NULL;

            if (case_sensitive)
            {
                replace_me = cJSON_DetachItemFromObjectCaseSensitive(target, patch_child->string);
            }
            else
            {
                replace_me = cJSON_DetachItemFromObject(target, patch_child->string);
            }

            replacement = merge_patch(replace_me, patch_child, case_sensitive);
            if (replacement == NULL)
            {
                return NULL;
            }

            cJSON_AddItemToObject(target, patch_child->string, replacement);
        }
        patch_child = patch_child->next;
    }
    return target;
}

/* 
 * Apply a JSON Merge Patch (RFC 7386) to a cJSON object (case-insensitive)
 * This function provides the public API for JSON Merge Patch functionality:
 * 1. Takes an object to modify and a patch object
 * 2. Delegates to the internal merge_patch function
 * 3. Uses case-insensitive matching for object member names
 * 4. Returns a new cJSON object representing the merged result
 * JSON Merge Patch is a simpler alternative to JSON Patch (RFC 6902) for many use cases:
 * - Uses a single patch object instead of an array of operations
 * - More intuitive for simple modifications
 * - Automatically handles object creation and deletion
 * Note: This function never modifies the input objects, returning a new object instead
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatch(cJSON *target, const cJSON * const patch)
{
    /* Delegate to internal merge_patch with case-insensitive comparison */
    return merge_patch(target, patch, false);
}

/* 
 * Apply a JSON Merge Patch (RFC 7386) to a cJSON object (case-sensitive)
 * This function provides the public API for JSON Merge Patch functionality:
 * 1. Takes an object to modify and a patch object
 * 2. Delegates to the internal merge_patch function
 * 3. Uses case-sensitive matching for object member names (unlike cJSONUtils_MergePatch)
 * 4. Returns a new cJSON object representing the merged result
 * JSON Merge Patch is a simpler alternative to JSON Patch (RFC 6902) for many use cases:
 * - Uses a single patch object instead of an array of operations
 * - More intuitive for simple modifications
 * - Automatically handles object creation and deletion
 * Note: This function never modifies the input objects, returning a new object instead
 * The case-sensitive version treats 'A' and 'a' as different keys in object matching
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_MergePatchCaseSensitive(cJSON *target, const cJSON * const patch)
{
    /* Delegate to internal merge_patch with case-sensitive comparison */
    return merge_patch(target, patch, true);
}

/* 
 * Generate a JSON Merge Patch (RFC 7386) to transform one cJSON structure into another
 * This function implements the core logic for generating JSON Merge Patches:
 * 1. Compares two cJSON structures ('from' and 'to')
 * 2. Creates a patch object that describes the differences
 * 3. Handles all JSON types and structures recursively
 * 4. Supports both case-sensitive and case-insensitive comparisons
 * 5. Properly handles added, removed, and changed members
 * The generated patch can be applied using cJSONUtils_MergePatch to transform 'from' into 'to'
 */
static cJSON *generate_merge_patch(cJSON * const from, cJSON * const to, const cJSON_bool case_sensitive)
{
    cJSON *from_child = NULL;   /* Current child in the 'from' object */
    cJSON *to_child = NULL;     /* Current child in the 'to' object */
    cJSON *patch = NULL;        /* The generated patch object */
    
    /* Handle NULL 'to' case - patch to delete everything */
    if (to == NULL)
    {
        return cJSON_CreateNull();
    }
    
    /* Handle cases where either 'from' or 'to' is not an object */
    if (!cJSON_IsObject(to) || !cJSON_IsObject(from))
    {
        return cJSON_Duplicate(to, 1);
    }

    /* Sort both objects to ensure consistent member ordering */
    sort_object(from, case_sensitive);
    sort_object(to, case_sensitive);

    /* Initialize iteration pointers */
    from_child = from->child;
    to_child = to->child;
    
    /* Create the patch object */
    patch = cJSON_CreateObject();
    if (patch == NULL)
    {
        return NULL;  /* Memory allocation failed */
    }
    
    /* Iterate through both objects simultaneously */
    while (from_child || to_child)
    {
        int diff;  /* Comparison result between current keys */
        
        /* Determine which key is lexicographically smaller */
        if (from_child != NULL)
        {
            if (to_child != NULL)
            {
                diff = strcmp(from_child->string, to_child->string);
            }
            else
            {
                diff = -1;  /* Only 'from' has an element */
            }
        }
        else
        {
            diff = 1;  /* Only 'to' has an element */
        }

        if (diff < 0)
        {
            /* 'from' has a value that 'to' doesn't have -> remove it */
            cJSON_AddItemToObject(patch, from_child->string, cJSON_CreateNull());

            from_child = from_child->next;
        }
        else if (diff > 0)
        {
            /* 'to' has a value that 'from' doesn't have -> add it to patch */
            cJSON_AddItemToObject(patch, to_child->string, cJSON_Duplicate(to_child, 1));

            to_child = to_child->next;
        }
        else
        {
            /* Object key exists in both objects */
            if (!compare_json(from_child, to_child, case_sensitive))
            {
                /* Values are not identical --> generate a recursive patch */
                cJSON_AddItemToObject(patch, to_child->string, cJSONUtils_GenerateMergePatch(from_child, to_child));
            }

            /* Move to next key in both objects */
            from_child = from_child->next;
            to_child = to_child->next;
        }
    }
    
    /* Check if patch is empty */
    if (patch->child == NULL)
    {
        /* No patch generated - objects are equivalent */
        cJSON_Delete(patch);
        return NULL;
    }

    return patch;  /* Return the generated patch */
}

/* 
 * Generate a JSON Merge Patch (RFC 7386) to transform one cJSON structure into another (case-insensitive)
 * This function provides the public API for generating JSON Merge Patches:
 * 1. Takes two cJSON structures ('from' and 'to')
 * 2. Delegates to the internal generate_merge_patch function
 * 3. Uses case-insensitive comparison for object member names
 * 4. Returns a patch object that can be applied using cJSONUtils_MergePatch
 * JSON Merge Patch is a simpler alternative to JSON Patch (RFC 6902):
 * - Uses a single patch object instead of an array of operations
 * - More intuitive for simple modifications
 * - Automatically handles object creation and deletion
 * The generated patch describes the minimal changes needed to transform 'from' into 'to'
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatch(cJSON * const from, cJSON * const to)
{
    /* Delegate to internal generate_merge_patch with case-insensitive comparison */
    return generate_merge_patch(from, to, false);
}

/* 
 * Generate a JSON Merge Patch (RFC 7386) to transform one cJSON structure into another (case-sensitive)
 * This function provides the public API for generating JSON Merge Patches:
 * 1. Takes two cJSON structures ('from' and 'to')
 * 2. Delegates to the internal generate_merge_patch function
 * 3. Uses case-sensitive comparison for object member names (unlike cJSONUtils_GenerateMergePatch)
 * 4. Returns a patch object that can be applied using cJSONUtils_MergePatchCaseSensitive
 * JSON Merge Patch is a simpler alternative to JSON Patch (RFC 6902):
 * - Uses a single patch object instead of an array of operations
 * - More intuitive for simple modifications
 * - Automatically handles object creation and deletion
 * The generated patch describes the minimal changes needed to transform 'from' into 'to'
 * The case-sensitive version treats 'A' and 'a' as different keys in object matching
 */
CJSON_PUBLIC(cJSON *) cJSONUtils_GenerateMergePatchCaseSensitive(cJSON * const from, cJSON * const to)
{
    /* Delegate to internal generate_merge_patch with case-sensitive comparison */
    return generate_merge_patch(from, to, true);
}
